package com.learn._2list;


import com.learn.TestTool;

import java.util.Random;

/**
 * 线性表   顺序存储结构实现
 */
public class ArrayList<T> implements List<T> {

    private static final int INIT_SIZE = 10;

    private Object[] array;
    private int curr = 0;

    //线性表的最大数量，一般不用
    //private int max = -1;

    //创建
    public ArrayList(){
        this(INIT_SIZE);
    }

    public ArrayList(int initSize){
        expandSize(initSize);
    }

    //查询相关：三种基本接口，根据idx查元素， 根据元素查idx，  是否存在元素

    //查询:根据idx查元素       时间复杂度 1
    public T get(int idx){
        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        return (T)array[idx];
    }

    //查询 根据元素查idx         时间复杂度  n  平均n/2
    public int indexOf(T obj){

        if(obj == null){
            return -1;
        }
        int tmpIdx = 0;
        while(tmpIdx < curr){
            if(obj.equals(array[tmpIdx])){
                return tmpIdx;
            }
            tmpIdx ++;
        }
        return -1;
    }

    //查询 是否存在 ,重用indexOf 或者自己写            同indexof
    public boolean contains(T obj){
        return indexOf(obj) != -1;
    }

    @Override
    public boolean empty() {
        return size() == 0;
    }

    @Override
    public int size() {
        return curr;
    }


    //增加元素， 尾部增， 下标增

    //增加元素：尾部增           时间复杂度 1
    public void add(T obj){
        if(curr == array.length){
            expandSize(nextSize());
        }

        array[curr ++] = obj;
    }

    //增加元素，下标增           时间复杂度 n 平均 n/2 但是java里，提供了内存的直接整块复制的技术，因此实际是会比这个快的，快在材质不在算法
    public void add(int idx,T obj){
        if(idx > curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }

        if(curr >= array.length){
            expandSize(nextSize());
        }

        rightMoveFromIdx(idx);
        array[idx] = obj;
        curr ++;
    }


    //删除元素 ： 直接删，下标删

    //删除元素： 直接删          时间复杂度   n
    public void remove(T obj){
        remove(indexOf(obj));
    }


    //删除元素 ： 下标删           时间复杂度  n/2 但是java里，提供了内存的直接整块复制的技术，因此实际是会比这个快的，快在材质不在算法
    public void remove(int idx){
        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }

        leftMoveFromIdx(idx + 1);
        curr --;
        //还是释放掉吧
        array[curr] = null;
    }



    //修改元素                        时间复杂度 1

    public void set(int idx, T obj){
        if(idx >= curr || idx < 0){
            throw new RuntimeException("invalid idx");
        }
        array[idx] = obj;
    }



    // 清理
    public void clear(){
        int tmp=0;
        while(tmp < curr){
            array[tmp ++] = null;
        }
        curr = 0;
    }


    //addAll 和 removeall的优化



    //可优化的内部策略

    //扩张策略
    private int nextSize() {
        int tmp;
        return ((tmp = (int)(array.length * 1.5))>array.length)? tmp : tmp + 1;
    }


    private void expandSize(int size) {

        if(array == null){
            array = new Object[size];
        }else{
            Object[] tmp = new Object[size];
            System.arraycopy(array,0,tmp,0,curr);
            array = tmp;
        }


    }

    //复制策略  更底层内存复制还是java层一个个复制
    private void rightMoveFromIdx(int idx) {
        /*int tmp = curr;
        while(tmp > idx){
            array[tmp] = array[tmp - 1];
            tmp --;
        }*/
        //注意这里的system.arraycopy 的效率要远比自己写的一个个move要来得快得多，是直接的连续内存的复制
        //System#arraycopy 是直接对内存中的数据块进行复制的，是一整块一起复制的，它是采用本地编码实现的。
        //
        //而采用下标一个一个地进行赋值时，时间主要浪费在了寻址和赋值上。
        //
        //因此，建议复制数组或者动态增加数组长度时，采用 System#arraycopy 方法。
        //
        //像我们常用的 ArrayList 内部就是采用数组存储的，在满掉的时候，就采用 System#arraycopy 来动态
        //增加其内部存储容量的。
        System.arraycopy(array,idx,array,idx + 1,curr - idx);
    }

    private void leftMoveFromIdx(int idx) {
        /*while(idx < curr){
            array[idx - 1] = array[idx];
            idx ++;
        }*/
        System.arraycopy(array,idx,array,idx -1,curr - idx);
    }



    public static void main(String[] args) {
        java.util.ArrayList javaList = new java.util.ArrayList();
        ArrayList arrayList = new ArrayList();


        int num = 100000;
        int range = 1000000;
        int circleNum = 100;
        Integer[] array = new Integer[num];
        Random rand = new Random();
        int tmp = 0;
        int tmpNum = num;
        while(tmpNum -- > 0){
            array[tmp ++] = rand.nextInt(range);
        }

        for(Integer i :array){
            javaList.add(i);
            arrayList.add(i);
        }


        //查找测试
    /*    TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                arrayList.contains(i);
            }
        },1,"my contains ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                javaList.contains(i);
            }
        },1,"java contains ");*/
        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                arrayList.get(i);
            }
        },1,"my  ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                javaList.get(i);
            }
        },1,"java ");*/

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                arrayList.indexOf(i);
            }
        },1,"my  ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < circleNum;i ++){
                javaList.indexOf(i);
            }
        },1,"java ");*/

        //增测试

        /*TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                javaList.add(i);
            }
            for(int i = 0;i < circleNum; i ++){
                javaList.add(i,i);
            }
        },1,"java ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                arrayList.add(i);
            }
            for(int i = 0;i < circleNum; i ++){
                arrayList.add(i,i);
            }
        },1,"my  ");*/






        //修改测试

       /* TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                arrayList.add(i);
            }
            for(int i = 0;i < num; i ++){
                arrayList.set(i,i);
            }
        },1,"my  ");


        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num;i ++){
                javaList.add(i);
            }
            for(int i = 0;i < num; i ++){
                javaList.set(i,i);
            }
        },1,"java ");*/



        //删测试

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num; i ++){
                arrayList.add(i);
            }

            for(int i = 0;i < num; i ++){
                arrayList.remove(new Integer(i));
            }
            arrayList.clear();
        },1,"my  ");

        TestTool.testAndPrintTime(()->{
            for(int i = 0;i < num; i ++){
                javaList.add(i);
            }

            for(int i = 0;i < num; i ++){
                javaList.remove(new Integer(i));
            }
            javaList.clear();
        },1,"java ");







    }


}
